package com.practice.sequence;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MergeInterval {
	public int[][] merge(int[][] intervals) {
		ArrayList<Interval> list = new ArrayList<Interval>();
		for (int i=0; i<intervals.length; i++) {
			list.add(new Interval(intervals[i][0], intervals[i][1]));
		}
		
		Collections.sort(list, new Comparator<Interval>() {
			public int compare(Interval a, Interval b) {
				return a.begin - b.begin;
			}
		});
		
		ArrayList<Interval> merged = new ArrayList<Interval>();
		
		for (int i=0; i<list.size(); ) {
			Interval current = list.get(i);
			int end = current.end;
			int j = i+1;
			while (j<list.size()) {
				Interval next = list.get(j);
				if (next.begin > end) break;
				if (end < next.end) end = next.end;
				j++;
			}
			
			merged.add(new Interval(current.begin, end));
			i = j;
		}
		
		int[][] s = new int[merged.size()][2];
		for (int i=0; i<merged.size(); i++) {
			s[i][0] = merged.get(i).begin;
			s[i][1] = merged.get(i).end;
		}
		return s;
	}
	
	private class Interval {
		public int begin;
		public int end;
		
		public Interval(int begin, int end) {
			this.begin = begin;
			this.end = end;
		}
	}
}
